package sum3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    	List<List<Integer>> ans=new ArrayList<List<Integer>>();
    	int[][] first=new int[2][99999];
    	int[][] second=new int[2][99999];
    	boolean[] boFirst=new boolean[99999];
    	boolean[] boSecond=new boolean[99999];
    	for (int i=0;i<first[0].length;i++){
    		first[0][i]=-1; second[0][i]=-1;
    		first[1][i]=-1; second[1][i]=-1;
    	}
    	Arrays.sort(nums);
    	for (int i=0;i<nums.length;i++)
    		for (int j=i+1;j<nums.length;j++){
    			int result=nums[i]+nums[j];
    			int flag=1; 
    			if (result<0) {flag=0;  result=-result;}
    			while (first[flag][result]!=-1)
    				result++;
    			first[flag][result]=i;
    			second[flag][result]=j;
    		}
    	for (int i=0;i<nums.length;i++){
    		int target=nums[i];
    		int flag=1;
            if (target<0) {flag=0; target=-target;}
            while (first[flag][target]!=-1){
            	if (nums[first[flag][target]]+nums[second[flag][target]]==-nums[i])
            		if (i!=first[flag][target] && i!=second[flag][target]){
            			Integer[] temp=new Integer[3];
            			temp[0]=nums[first[flag][target]];
            			temp[1]=nums[second[flag][target]];
            			temp[2]=nums[i];
            			Arrays.sort(temp);
            			Boolean bo=true;
            			for (List<Integer> ex:ans)
            				if ((ex.get(0)==temp[0]) && (ex.get(1)==temp[1])) bo=false;
            			if (bo) ans.add(Arrays.asList(temp));
            		}
            	target++;
            }
    	}
    	
    	return ans;
    }

    public static void main(String args[]){
    	Solution so=new Solution();
    	int[] nums=new int[]{1,0,-1};
    	so.threeSum(nums);
    }
}

/* sum3 hash理论能解（n^2+n*k)。。估计是哈希写得太烂了TAT */
